Journals
  Publication Years
  Keywords
Search within results Open Search
Please wait a minute...
For Selected: Toggle Thumbnails
Evolutionary algorithm based on approximation technique for solving bilevel programming problems
Yu SHEN, Hecheng LI, Lijuan CHEN
Journal of Computer Applications    2022, 42 (8): 2511-2518.   DOI: 10.11772/j.issn.1001-9081.2021061079
Abstract292)   HTML2)    PDF (701KB)(90)       Save

Bilevel programming involves two optimization problems located at upper-level (leader) and lower-level (follower). The constraint domain of the leader is determined by the follower implicitly, the leader objective dominates in a bilevel optimization procedure, and the follower objective must be optimized with respect of the follower variables. The hierarchical structure of the bilevel optimization problem causes large computational complexity. Especially, the frequent computations of the follower can accumulate a large amount of computational cost. In order to solve this kind of problem effectively, an evolutionary algorithm based on approximation technique was developed. Firstly, a multi-population co-evolution approach was applied, and the crossover and the mutation operators were used respectively to balance the exploitation and exploration capabilities of the algorithm. Secondly, based on the sensitivity analysis theory, an approximation evaluation method for new individuals was designed to reduce the computation frequency of the follower carried out by the algorithm. The demonstration results of the approximate effect of a numerical example show that most positions of the approximate offspring individuals and the exact offspring individual are mostly coincident. In addition, the results on 10 common examples show that the proposed algorithm can find better optimal solutions than the multi-valued mapping algorithm. CPU time comparison shows that the approximate technique improves the speed of finding the optimal solution effectively, thereby reducing the running time. Therefore, the effectiveness of the approximate technique adopted by the algorithm is demonstrated.

Table and Figures | Reference | Related Articles | Metrics